package com.by.hashset;

/**
 * @version 1.0
 * @Author 彭彦彬
 * @Date 2025/4/9 17:45
 * @注释
 */
import java.util.LinkedList;

public class MyHashSet<E> {
    private static final int DEFAULT_CAPACITY = 8; // 默认容量
    private static final double LOAD_FACTOR = 0.75; // 负载因子

    private LinkedList<E>[] buckets; // 使用链表数组存储元素
    private int size; // 当前元素数量
    private int capacity; // 当前容量

    public MyHashSet() {
        this(DEFAULT_CAPACITY);
    }

    @SuppressWarnings("unchecked")
    public MyHashSet(int capacity) {
        this.capacity = capacity;
        this.buckets = new LinkedList[capacity];
        for (int i = 0; i < capacity; i++) {
            buckets[i] = new LinkedList<>(); // 初始化每个桶为一个链表
        }
        this.size = 0;
    }

    /**
     * 添加元素
     */
    public boolean add(E element) {
        if ((double) size / capacity >= LOAD_FACTOR) {
            resize(); // 如果负载因子超过阈值，则扩容
        }

        int index = hash(element); // 计算哈希索引
        LinkedList<E> bucket = buckets[index];

        // 检查是否已存在相同的元素
        if (bucket.contains(element)) {
            return false; // 已存在，不添加
        }

        // 如果不存在，则添加新元素
        bucket.add(element);
        size++;
        return true;
    }

    /**
     * 删除元素
     */
    public boolean remove(E element) {
        int index = hash(element); // 计算哈希索引
        LinkedList<E> bucket = buckets[index];

        if (bucket.remove(element)) { // 如果成功移除
            size--;
            return true;
        }

        return false; // 如果未找到元素
    }

    /**
     * 判断是否包含某个元素
     */
    public boolean contains(E element) {
        int index = hash(element); // 计算哈希索引
        LinkedList<E> bucket = buckets[index];

        return bucket.contains(element); // 检查桶中是否存在该元素
    }

    /**
     * 获取当前集合的大小
     */
    public int size() {
        return size;
    }

    /**
     * 判断集合是否为空
     */
    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * 动态扩容
     */
    @SuppressWarnings("unchecked")
    private void resize() {
        capacity *= 2; // 容量翻倍
        LinkedList<E>[] newBuckets = new LinkedList[capacity];
        for (int i = 0; i < capacity; i++) {
            newBuckets[i] = new LinkedList<>();
        }

        // 将旧的元素重新分配到新的桶中
        for (LinkedList<E> bucket : buckets) {
            for (E element : bucket) {
                int newIndex = hash(element);
                newBuckets[newIndex].add(element);
            }
        }

        buckets = newBuckets; // 更新桶数组
    }

    /**
     * 哈希函数：计算元素的哈希值并映射到桶的索引
     */
    private int hash(E element) {
        return Math.abs(element.hashCode()) % capacity;
    }

    public static void main(String[] args) {
        MyHashSet<Integer> set = new MyHashSet<>();
        set.add(10);
        set.add(20);
        set.add(30);

        System.out.println("Size: " + set.size()); // 输出 3
        System.out.println("Contains 20: " + set.contains(20)); // 输出 true
        System.out.println("Contains 40: " + set.contains(40)); // 输出 false

        set.remove(20);
        System.out.println("After removing 20, size: " + set.size()); // 输出 2
        System.out.println("Contains 20: " + set.contains(20)); // 输出 false
    }
}
